package com.lw.leetcode.arr.b;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * arr
 * 911. 在线选举
 *
 * @author liw
 * @version 1.0
 * @date 2022/1/19 22:35
 */
public class TopVotedCandidate {

    private List<Integer> tops;
    private int[] times;

    public TopVotedCandidate(int[] persons, int[] times) {
        tops = new ArrayList<>(persons.length);
        Map<Integer, Integer> voteCounts = new HashMap<>();
        voteCounts.put(-1, -1);
        int top = -1;
        for (int p : persons) {
            voteCounts.put(p, voteCounts.getOrDefault(p, 0) + 1);
            if (voteCounts.get(p) >= voteCounts.get(top)) {
                top = p;
            }
            tops.add(top);
        }
        this.times = times;
    }

    public int q(int t) {
        int l = 0;
        int r = times.length - 1;
        while (l < r) {
            int m = l + (r - l + 1) / 2;
            if (times[m] <= t) {
                l = m;
            } else {
                r = m - 1;
            }
        }
        return tops.get(l);
    }

}
